public class MyList {

     class ListNode {
     public int val;
     public ListNode next;
         public ListNode(int val) {
             this.val = val;
         }
     }
     //删除所有重复结点
    //oj连接：https://leetcode.cn/problems/remove-duplicates-from-sorted-list/submissions/
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) {
            return null;
        }
        if(head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast != null) {
            while(fast != null && fast.val == slow.val) {
                fast = fast.next;
            }
            if(fast != null) {
                slow.next = fast;
                slow = fast;
                fast = fast.next;
            }else {
                slow.next = null;
            }
        }
        return head;
    }
    //删除某个值：https://leetcode.cn/problems/shan-chu-lian-biao-de-jie-dian-lcof/submissions/
    public ListNode deleteNode(ListNode head, int val) {
        if(head == null) {
            return null;
        }
        if(head.val == val) {
            head = head.next;
            return head;
        }
        ListNode cur = head.next;
        ListNode curPrev = head;
        while(cur != null) {
            if(cur.val == val) {
                curPrev.next = cur.next;
                return head;
            }
            curPrev = cur;
            cur = cur.next;
        }
        return head;

    }
    //https://leetcode.cn/problems/LGjMqU/submissions/
    public void reorderList(ListNode head) {
        if(head == null) {
            return;
        }
        if(head.next == null || head.next.next == null) {
            return;
        }
        //有3个节点以上
        //1.找中间结点
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //2.翻转slow后面的链表
        ListNode cur = slow.next;
        slow.next = null;
        ListNode curNext = null;
        ListNode tmp = slow;//新的头
        while(cur != null) {
            curNext = cur.next;
            cur.next = tmp;
            tmp = cur;
            cur = curNext;
        }
        //3.重新排序
        cur = tmp;
        ListNode headNext = head;
        while(cur != slow) {
            cur = cur.next;
            tmp.next = headNext.next;
            headNext.next = tmp;
            headNext = tmp.next;
            tmp = cur;
        }

    }



}
